Comunicación No Estructurada
Elementos Finitos en Ingeniería
Patrón de comunicaciones complejo, que puede variar con el tiempo
Se complican las operaciones de aglomeración/asignación y proyección
Checklist del diseño de comunicaciones
1) Realizan todas las tareas aproximadamente el mismo número
de comunicaciones?
2) Cada tarea se comunica sólo con un pequeño número de ve-
cinos?
3) Pueden proceder las operaciones de comunicación de forma
simultánea?
4) Los cálculos asociados a diferentes tareas, puede proceder
concurrentemente?
Aglomeración/Asignación
Agrupación de Tareas en Procesos:
El número de procesos puede diferir del número de procesadores (multipro-
gramación)
Interacción entre procesos pertenecientes a diferentes aplicaciones
El número de procesos puede variar durante la ejecución de la aplicación
La aglomeración especifica un mecanismo por
el cual las tareas se asignan a procesos, o son
seleccionadas por los procesos durante la ejecución
Criterios que guían la Aglomeración:
Aumento de la Granularidad: Los costes de comunicación, sincronización y
y creación/gestión de procesos influyen críticamente en el rendimiento paralelo.
Flexibilidad/Escalabilidad
Costes de Desarrollo
Aumento de la Granularidad
Efecto Superficie-a-Volumen
Las comunicaciones son proporcionales
a la superficie del subdominio, mientras
que las computaciones lo son al volumen.
Aumento de la Granularidad
Replicación de Computación
Substitución de comunicaciones por computaciones redundantes
Ejemplo: Reducción Paralela
S = ? Xi
N-1
i =0
0
2
1
3
1
0
3
2
S S S R R R
0
2
1
3
0
2
1
3
Soluciones sin replicación
Array: 2(N-1) pasos
Arbol:2logN pasos
S
S
S
S
S
S
R
R
R
R
R
R
Aumento de la Granularidad
Replicación de Computación
Ejemplo: Reducción Paralela
Solución con replicación
Mariposa: logN pasos
Aumento de la Granularidad
Eliminación de Comunicaciones
Aglomeración de tareas no concurrentes (ej., a diferentes niveles de una estruc-
tura de computación)
Ejemplo: Reducción Paralela
Tareas no concurrentes aglomeradas
0
2
1
3
5
4
7
6
0
2
1
3
5
4
7
6
0
2
1
3
5
4
7
6
2
2
2
2
0
0
0
0
1
1
1
1
Hipercubo
Mariposa
Arbol
0
0
0
0
1
1
2
0
0
0
0
1
1
1
1
1
2
2
2
2
Perservando la flexibilidad
No restringir innecesariamente la escalabilidad del algoritmo (la
descomposición multidimensional es crítica)
La capacidad de crear un número variable de tareas es crítica para
asegurar la portabilidad y escalabilidad (permite realizar tareas como
simultanear computación y comunicación)
Todavía requerimos que haya más tareas que procesadores para ase-
gurar una buena capacidad de balancear la carga
La granularidad puede controlarse en tiempo de compilación o de
ejecución.
Reduciendo los costes de desarrollo
Diferentes estrategias de partición suelen tener costes de
desarrollo distintos (seleccionar aquella que evite cambios
extensos en el código)
Normalmente los algoritmos paralelos forman parte de
grandes aplicaciones, por tanto hay que evaluar los costes
de integración con los restantes módulos de la aplicación.
Checklist del diseño de la aglomeración
1) Ha reducido la aglomeración los costes de comunicaciones aumentando la
localidad?. Sino, estudie otra estrategia.
2) Si la aglomeración ha replicado computaciones (y datos), verifique que ésto
es eficiente para un amplio abanico de problemas y plataformas.
3) Si ha replicado los datos, compruebe que ésto no restringe la escalabilidad
de la aproximación
4) Son las tareas resultantes de similar costo en comunicaciones y computación?
5) El número de tareas aglomeradas, todavía escala con el tamaño del problema?
6) Si la aglomeración ha eliminado oportunidades de ejecución simultánea, ha
verificado si todavía hay suficiente concurrencia para un rango amplio de pla-
taformas?
7) Puede reducirse el número de tareas aún mas?
8) Si está paralelizando un código secuencial existente, ha evaluado sus costes?.
Si son altos, ha considerado otras estrategias totalmente diferentes?
Proyección
La proyección es Crítica en Máquinas Escalables
Aspectos de la Proyección de Procesos
¿Qué procesos deben ejecutarse en el mismo procesador? (multiprogramación,.)
¿Qué procesos se ejecutan en un procesador concreto?
Estrategias de Proyección
Situar procesos concurrentes en procesadores diferentes (potenciar la concu-
rrencia)
Situar procesos que comunican frecuentemente en el mismo procesador (po-
tenciar la localidad)
El problema de la Proyección es NP-Completo
Proyección
Estrategias de Proyección
Descomposición Estructurada en Dominios:
Proyección directa, minimizando comunicaciones.
Descomposición No-Estructurada Estática en Dominios:
Heurística de proyección con algún esquema estático de
balanceo de la carga.
Descomposición No-Estructurada Dinámica en Dominios:
Heurística de proyección con algún esquema dinámico de
balanceo de la carga
Descomposición Funcional:Heurística de proyección con
algún esquema de planificación de tareas estático o dinámico.
Algoritmo de Balanceo
de la Carga Computacional
Técnicas especialmente diseñadas para desarrollar programas
paralelos SPMD basados en la descomposición de dominios.
Engloban las fases de particionamiento, aglomeración y pro-
yección, y suelen denominarse algoritmos de particionamiento.
Aproximaciones Representativas
Algoritmos Regulares Estáticos
– Particionamiento por Bloques
– Particionamiento Cíclico (scattered)
Algoritmos Irregulares Estáticos
– Bisección Recursiva
Algoritmos Dinámicos
– Algoritmos Locales
– Métodos Probabilísticos
Particionamiento por Bloques
Características
Los procesos tienen una duración temporal determinable durante la fase
de compilación
Las comunicaciones son estructuradas (regulares)
Modelo de Programación:
SPMD estático
Particionamiento Cíclico (Scattered)
Características
Los procesos tienen una duración temporal determinable durante la fase
de compilación
Las comunicaciones son estructuradas (regulares)
Modelo de Programación:
SPMD estático
Bisección Recursiva
Características
Los procesos tienen una duración temporal determinable durante la fase de
compilación
Las comunicaciones son no estructuradas (irregulares)
Modelo de Programación: SPMD estático
Técnicas de Bisección Recursiva
Bisección de Coordenadas Recursiva: Descomposición del dominio en fun-
ción de la distancia Euclidiana entre sus elementos (las comunicaciones no
son optimizadas)
Bisección Gráfica Recursiva: Descomposición del dominio en función de la
conectividad entre sus elementos (reduce las necesidades de comunicación)
Bisección Espectral Recursiva: Descomposición del dominio en función de
sus propiedades espectrales (mejora la compacidad de los subdominios)
Bisección de Coordenadas Recursiva
Procedimiento
1. Determina la expansión más larga del dominio
2. Ordena los nodos de acuerdo con la coordenada seleccio-
nada
3. Asigna la mitad de los nodos ordenados a cada subdo-
minio
4. Repite recursivamente
Bisección Gráfica Recursiva
Procedimiento
1. Determina dos nodos periféricos del dominio
2. Ordena el resto de los nodos según la distancia gráfica
a los nodos seleccionados
3. Asigna la mitad de los nodos ordenados a cada subdo-
minio
4. Repite recursivamente
Bisección Espectral Recursiva
Procedimiento
1. Determina el vector de Fiedler del dominio usando el
algoritmo de Lanczos
2. Ordena los nodos de acuerdo con el tamaño de los ele-
mentos del vector de Fiedler
3. Asigna la mitad de los nodos ordenados a cada subdo-
minio
4. Repite recursivamente
Algoritmos Locales (Dinámicos)
Características
Los procesos tienen una duración temporal no determinable durante la fase
de compilación
Solución
Los procesadores comparan
periódicamente su carga compu-
tacional, y establecen una redis-
tribución para balancearla.
Planificación de Tareas
Características
Muchas tareas con requerimientos débiles de localidad
Distribución de Tareas entre Procesadores
Conflicto entre ejecución independiente (reducir costes de comunicación)
y conocimiento global del estado de computación (mejorar el balanceo
de la carga)
Esquemas de Planificación
Centralizado: Gestor/Trabajador
Distribuido: Las tareas se distribuyen entre los procesadores y se ejecu-
tan de forma cooperativa dinámica.
Problema de la Terminación de la Ejecución
Checklist del diseño de la proyección
1) Si ha considerado un diseño SPMD y es muy complejo, ha
considerado uno basado en la creación dinámica de tareas?.
Lo recíproco.
2) Si usa un esquema de balanceo de la carga centralizado, ha
verificado que el master no es un cuello de botella?
3) Si usa un esquema dinámico de balanceo de la carga, ha eva-
luado su costo?. Intente usar esquema cíclicos o probabilísticos.
4) Si usa un esquema probabilístico, tiene un número razonable
de tareas? (al menos 10 veces más que procesadores)
 Página anterior | Volver al principio del trabajo | Página siguiente  |